package 力扣;

import sun.text.IntHashtable;

import java.lang.annotation.ElementType;
import java.lang.reflect.Array;
import java.util.*;

public class leetcode18 {
    public static void main(String[] args) {
        int[] ints=new int[]{1,0,-1,0,-2,2};
        fourSum(ints,0);

    }
    public static List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> lists=new ArrayList<>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            for (int j=i+1;j < nums.length; j++){
                int leftPoint=j+1;
                int rightPoint=nums.length-1;
                if((j+1)-(nums.length-1)>=1) break;
                while (true){
                    if(leftPoint>=rightPoint) break;
                    int sum=nums[i]+nums[j]+nums[leftPoint]+nums[rightPoint];

                    if(sum==target) {
                        List<Integer> list=new ArrayList<>();
                        list.add(nums[i]);
                        list.add(nums[j]);
                        list.add(nums[leftPoint]);
                        list.add(nums[rightPoint]);
                        if(lists.contains(list)) {
                            if(leftPoint+1<rightPoint){
                                leftPoint++;
                            }
                        }
                        else {
                            lists.add(list);
                            if(leftPoint+1<=rightPoint)
                                leftPoint++;
                        }

                    }
                    if(leftPoint+1<=rightPoint&&sum<target){
                        leftPoint++;
                    }
                    if(rightPoint-1>=leftPoint&&sum>target){
                        rightPoint--;
                    }
                }
            }
        }

        return lists;

    }

}
